package minDistance

/**
给你两个单词word1 和word2， 请返回将word1转换成word2 所使用的最少操作数。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

*/
func minDistance(word1 string, word2 string) int {
	w1 := len(word1)
	w2 := len(word2)
	if w1*w2 == 0 {
		return w1 + w2
	}
	// 给空串留个位置
	w1, w2 = w1+1, w2+1
	// 定义dp[i][j] 为word1的前i个字符转换到word2的前j个字符的最小距离
	dp := make([][]int, w1)
	for i := 0; i < w1; i++ {
		dp[i] = make([]int, w2)
		dp[i][0] = i
	}
	for i := 0; i < w2; i++ {
		dp[0][i] = i
	}
	for i := 1; i < w1; i++ {
		for j := 1; j < w2; j++ {
			add := 0
			// 判断是否需要修改
			if word1[i-1] != word2[j-1] {
				add = 1
			}
			//根据对称性，word1增加=word2删除，word2增加=word1删除 word1修改=word2修改
			//所以达到dp[i][j]的方法只有三种情况
			//1、word1增加1个字符 2、word2增加一个字符 3、word1修改一个字符
			// +1 指的是增加一个字符，操作数+1
			// +add 指的是修改一个字符后，最多还存在add个操作数达到对应的字符
			dp[i][j] = min(dp[i-1][j]+1, min(dp[i][j-1]+1, dp[i-1][j-1]+add))
		}
	}
	return dp[w1-1][w2-1]
}

/* 从dp[i][j] = min(dp[i-1][j]+1,min(dp[i][j-1]+1,dp[i-1][j-1] +add)) 可以看到
   dp[i][j]只与他的左边、上边、左上有关联
	所以考虑只用一维dp[]来优化空间
	dp[i-1]对应 dp[i-1][j]  dp[i]对应dp[i][j-1]，并不断更新自己
	dp[i-1][j-1] 使用额外的lu来保存值
*/
func minDistance2(word1 string, word2 string) int {
	w1 := len(word1)
	w2 := len(word2)
	if w1*w2 == 0 {
		return w1 + w2
	}
	// 给空串留个位置
	w1, w2 = w1+1, w2+1
	// dp[i]表示对于word2前i个字符的最少操作数
	dp := make([]int, w2)
	// 初始化dp数组，当word1为空串的时候，dp[i]等于word2的长度
	for i := 0; i < w2; i++ {
		dp[i] = i
	}
	var lu int
	for i := 1; i < w1; i++ {
		lu = dp[0]
		dp[0] = i
		for j := 1; j < w2; j++ {
			if word1[i-1] != word2[j-1] {
				lu++
			}
			dp[j], lu = min(dp[j]+1, min(dp[j-1]+1, lu)), dp[j]
		}
	}
	return dp[w2-1]
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}
